/*
 * @Author: your name
 * @Date: 2020-09-09 15:23:05
 * @LastEditTime: 2020-09-10 09:38:55
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: /CountingSort/CountSort.cpp
 */
#include <iostream>
#include <vector>
using namespace std;

void countSort(vector<int>& vec) 
{
    // 数量少于两个直接返回
	if (vec.size() < 2) 
	{
		return;
	}
    
	int min = vec[0];  // 定义最小值并初始化
	int max = vec[0];  // 定义最大值并初始化
    // 查找数组中的最小值和最大值
	for (int i = 0; i < vec.size(); i++) 
	{
		min = min < vec[i] ? min : vec[i];   
		max = max > vec[i] ? max : vec[i];
	}
	// 如果最大值和最小值相等，表示数组中的数字都是相同的，直接返回
	if (min == max) 
	{
		return;
	}

	vector<int> countVec(max - min + 1, 0);  // 开辟一个max-min+1长度大小的数组，并初始化

    // 遍历数组中的每个元素并计数
	for (int i = 0; i < vec.size(); i++)
	{
		countVec[vec[i] - min]++;
	}
    
	int index = 0;  // 用于记录原始数组的下标
    // 把辅助数组更新到原数组中
	for (int i = 0; i < countVec.size(); i++) 
	{
        // 直到计数减为零，在进行下一次循环
		while (countVec[i]) {
			vec[index] = i+min; 
			index++;
			countVec[i]--;
		}
	}
}

int main()
{
    vector<int> arry={20,19,32,46,34,49,28,31};
    for (int i = 0; i < arry.size(); i++)
    {
        cout<<arry[i]<<" ";
    }
    cout<<endl;

    countSort(arry);
    for (int i = 0; i < arry.size(); i++)
    {
        cout<<arry[i]<<" ";
    }
    cout<<endl;
    
    return 0;
}